package 我的Java学习_算法基础.day_03;


import static 我的Java学习_算法基础.day_03._036_三点中值法.partition2;

public class _039_最快效率求出乱序数组中第k小的数 {
    public static void main(String[] args) {
        int[] a = {3,9,7,6,1,2};
        int k = selectK(a,0,a.length-1,6);
        System.out.println(k);
    }

    /**
     * 期望O(n) 最差O(n^2)
     * @param a 数组
     * @param begin 第一个元素下标
     * @param end   最后一个元素下标
     * @param key   第key小
     * @return  第key小的数
     */
    public static int selectK(int[] a,int begin,int end,int key){
        if(key<=end-begin+1){       //判断第k小的数是否存在
            int q = partition2(a,begin,end);    //三点中值分区法
            int qk = q - begin + 1;     //主元是第几个元素
            if(qk==key){
                return a[q];
            }else if(key<qk){
                return selectK(a,begin,q-1,key);
            }else{
                return selectK(a,q+1,end,key-qk);//第几个也要算上左区间和基元，需要划掉
            }
        }else{
            return -1;
        }

    }
}
